////////////////////////////////////////////////////////////////////////////////////////////////////
/// Copyright (c) 2009 - 2010 RacoonStudios
///
/// Permission is hereby granted, free of charge, to any person obtaining a copy of this
/// software and associated documentation files (the "Software"), to deal in the Software
/// without restriction, including without limitation the rights to use, copy, modify, merge,
/// publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons
/// to whom the Software is furnished to do so, subject to the following conditions:
///
/// The above copyright notice and this permission notice shall be included in all copies or
/// substantial portions of the Software.
///
/// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
/// INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
/// PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
/// FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
/// OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
/// DEALINGS IN THE SOFTWARE.
////////////////////////////////////////////////////////////////////////////////////////////////////

#pragma once
#ifndef dictionary_h__
#define dictionary_h__

#include "helper\array.h"
#include "helper\keyvaluepair.h"

namespace Helper
{
	////////////////////////////////////////////////////////////////////////////////////////////////////
	/// \class	Dictionary
	///
	/// \brief	This is the container class called Dictionary.
	///			It contains a sorted Array with KeyValuePairs. Also some key notes on 
	///			the performance:
	///			
	///			The Dictionary works with a sorted Array, that means it that we call the
	///			Array::Sort() after every object which is added to the Array. This will
	///			reduce the performance.
	///			For this issue there are the both functions BeginBulkAdd() and EndBulkAdd()
	///			which you should use when you want to add many items to the Dictionary.
	///			Within the process of a BulkAdd the Dictionary will not be sorted. It will 
	///			be sorted firstly when you close the BulkAdd and by that calling EndBulkAdd().
	///
	/// \author	Markus
	/// \date	21.02.2010
	////////////////////////////////////////////////////////////////////////////////////////////////////
	template<class KEYTYPE, class VALUETYPE> 
	class Dictionary
	{
	public:

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	Dictionary()
		///
		/// \brief	Default constructor. 
		///
		/// \author	Markus
		/// \date	21.02.2010
		////////////////////////////////////////////////////////////////////////////////////////////////////
		Dictionary();

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	Dictionary(const Dictionary<KEYTYPE, VALUETYPE>& rhs)
		///
		/// \brief	Constructor. 
		///
		/// \author	Markus
		/// \date	21.02.2010
		///
		/// \param	[in]	rhs	The right hand side object. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		Dictionary(const Dictionary<KEYTYPE, VALUETYPE>& rhs);





		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	void operator=(const Dictionary<KEYTYPE, VALUETYPE>& rhs)
		///
		/// \brief	Copy operator. 
		///
		/// \author	Markus
		/// \date	21.02.2010
		///
		/// \param	[in]	rhs	The right hand side object. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		void operator=(const Dictionary<KEYTYPE, VALUETYPE>& rhs);

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	VALUETYPE& operator[](const KEYTYPE& key)
		///
		/// \brief	Casting operator. 
		///			You will get full reading and writing access for the element.
		///
		/// \author	Markus
		/// \date	21.02.2010
		///
		/// \param	[in]	key	The key from which we want the value
		///
		/// \return	The corresponding value of the specified key.
		////////////////////////////////////////////////////////////////////////////////////////////////////
		VALUETYPE& operator[](const KEYTYPE& key);

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	const VALUETYPE& operator[](const KEYTYPE& key) const
		///
		/// \brief	Casting operator. 
		///			You will just get reading access for the element.
		///
		/// \author	Markus
		/// \date	21.02.2010
		///
		/// \param	[in]	key	The key from which we want the value. 
		///
		/// \return	The corresponding value of the specified key.
		////////////////////////////////////////////////////////////////////////////////////////////////////
		const VALUETYPE& operator[](const KEYTYPE& key) const;





		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	tSize Size() const
		///
		/// \brief	Returns the size of the dictionary.
		///
		/// \author	Markus
		/// \date	21.02.2010
		///
		/// \return	The size of the dictionary.
		////////////////////////////////////////////////////////////////////////////////////////////////////
		tSize Size() const;

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	void Clear()
		///
		/// \brief	Clears this dictionary.
		///			Thereby all destructors of all objects will be called.
		///
		/// \author	Markus
		/// \date	21.02.2010
		////////////////////////////////////////////////////////////////////////////////////////////////////
		void Clear();

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	bool IsEmpty() const
		///
		/// \brief	Query if the dictionary is empty. 
		///
		/// \author	Markus
		/// \date	21.02.2010
		///
		/// \return	True if the dictionary is empty, otherwise false.
		////////////////////////////////////////////////////////////////////////////////////////////////////
		bool IsEmpty() const;

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	void Reserve(tSize numElements)
		///
		/// \brief	Reserves the specified amount of element within the Dictionary. 
		///
		/// \author	Markus
		/// \date	21.02.2010
		///
		/// \param	[in]	numElements	The amount of element we want to reserve for later use.
		////////////////////////////////////////////////////////////////////////////////////////////////////
		void Reserve(tSize numElements);

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	void BeginBulkAdd()
		///
		/// \brief	This begins a bulk add. 
		///
		/// \author	Markus
		/// \date	21.02.2010
		////////////////////////////////////////////////////////////////////////////////////////////////////
		void BeginBulkAdd();

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	void Add(const KeyValuePair<KEYTYPE, VALUETYPE>& kvp)
		///
		/// \brief	This simply adds a KeyValuePair to the Dictionary.
		///
		/// \author	Markus
		/// \date	21.02.2010
		///
		/// \param	[in]	kvp	The KeyValuePair we want to add to the Dictionary.
		////////////////////////////////////////////////////////////////////////////////////////////////////
		void Add(const KeyValuePair<KEYTYPE, VALUETYPE>& kvp);

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	void Add(const KEYTYPE& key, const VALUETYPE& value)
		///
		/// \brief	This simple adds a KeyValuePair to the Dictionary which will first be
		///			built up from the specified key and value.
		///
		/// \author	Markus
		/// \date	21.02.2010
		///
		/// \param	[in]	key		The key we want to add to the Dictionary.
		/// \param	[in]	value	The keys responding value.
		////////////////////////////////////////////////////////////////////////////////////////////////////
		void Add(const KEYTYPE& key, const VALUETYPE& value);

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	void EndBulkAdd()
		///
		/// \brief	This ends the bulk add. 
		///
		/// \author	Markus
		/// \date	21.02.2010
		////////////////////////////////////////////////////////////////////////////////////////////////////
		void EndBulkAdd();

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	void Erase(const KEYTYPE& key)
		///
		/// \brief	This erases the KeyValuePair which contains the specified key.
		///
		/// \author	Markus
		/// \date	21.02.2010
		///
		/// \param	[in]	key	The key of the KeyValuePair which should be erased erase.
		////////////////////////////////////////////////////////////////////////////////////////////////////
		void Erase(const KEYTYPE& key);

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	void EraseAtIndex(tIndex index)
		///
		/// \brief	This erases the KeyValuePair at the specifid index if it's not out of
		///			boundery. Otherwise nothing will be done.
		///
		/// \author	Markus
		/// \date	21.02.2010
		///
		/// \param	[in]	index	The index of the KeyValuePair to erase.
		////////////////////////////////////////////////////////////////////////////////////////////////////
		void EraseAtIndex(tIndex index);

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	tIndex FindIndex(const KEYTYPE& key) const
		///
		/// \brief	This searches for the index of the KeyValuePair which contains the 
		///			specified key.
		///
		/// \author	Markus
		/// \date	21.02.2010
		///
		/// \param	[in]	key	The key we are looking for. 
		///
		/// \return	If the key was found its index will be returned, otherwise InvalidIndex.
		////////////////////////////////////////////////////////////////////////////////////////////////////
		tIndex FindIndex(const KEYTYPE& key) const;

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	bool Contains(const KEYTYPE& key) const
		///
		/// \brief	Determines if this Dictionary contains the specified key.
		///
		/// \author	Markus
		/// \date	21.02.2010
		///
		/// \param	[in]	key	The key to test for containment. 
		///
		/// \return	True if the key was found within the Dictionary, otherwise false.
		////////////////////////////////////////////////////////////////////////////////////////////////////
		bool Contains(const KEYTYPE& key) const;

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	const KEYTYPE& KeyAtIndex(tIndex index) const
		///
		/// \brief	This returns the key of the KeyValuePair at the specified index.
		///
		/// \author	Markus
		/// \date	21.02.2010
		///
		/// \param	[in]	index	The index from which we want the key.
		///
		/// \return	The key of the KeyValuePair at the specified index.
		////////////////////////////////////////////////////////////////////////////////////////////////////
		const KEYTYPE& KeyAtIndex(tIndex index) const;

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	VALUETYPE& ValueAtIndex(tIndex index)
		///
		/// \brief	This returns the value of the KeyValuePair at the specified index.
		///			With this function you will get full reading and writing access to 
		///			the element.
		///
		/// \author	Markus
		/// \date	21.02.2010
		///
		/// \param	[in]	index	The index from which we want the value.
		///
		/// \return	The value of the KeyValuePair at the specified index.
		////////////////////////////////////////////////////////////////////////////////////////////////////
		VALUETYPE& ValueAtIndex(tIndex index);

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	const VALUETYPE& ValueAtIndex(tIndex index) const
		///
		/// \brief	This returns the value of the KeyValuePair at the specified index.
		///			With this function you will only get reading access for the element.
		///
		/// \author	Markus
		/// \date	21.02.2010
		///
		/// \param	[in]	index	The index from which we want the value.
		///
		/// \return	The value of the KeyValuePair at the specified index.
		////////////////////////////////////////////////////////////////////////////////////////////////////
		const VALUETYPE& ValueAtIndex(tIndex index) const;

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	KeyValuePair<KEYTYPE, VALUETYPE>& KeyValuePairAtIndex(tIndex index) const
		///
		/// \brief	Key value pair at index. 
		///
		/// \author	Markus
		/// \date	21.02.2010
		///
		/// \param	[in]	index	The index of the queried KeyValuePair.
		///
		/// \return	THe KeyValuePair at the index.
		////////////////////////////////////////////////////////////////////////////////////////////////////
		KeyValuePair<KEYTYPE, VALUETYPE>& KeyValuePairAtIndex(tIndex index) const;

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	Array<KEYTYPE> KeysAsArray() const
		///
		/// \brief	Returns all keys of the dictionary packed into as Array.
		///
		/// \author	Markus
		/// \date	21.02.2010
		///
		/// \return	The keys of the dictionary as Array.
		////////////////////////////////////////////////////////////////////////////////////////////////////
		Array<KEYTYPE> KeysAsArray() const;

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	Array<VALUETYPE> ValuesAsArray() const
		///
		/// \brief	Returns all values of the dictionary packed into an Array.
		///
		/// \author	Markus
		/// \date	21.02.2010
		///
		/// \return	The values of the dictionary as Array.
		////////////////////////////////////////////////////////////////////////////////////////////////////
		Array<VALUETYPE> ValuesAsArray() const;

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	template<class RETURNTYPE> RETURNTYPE KeysAs() const
		///
		/// \brief	Returns the keys packed into the specified data type if this is possible.
		///
		/// \author	Markus
		/// \date	21.02.2010
		///
		/// \return	The keys of the dictionary as the specified data type.
		////////////////////////////////////////////////////////////////////////////////////////////////////
		template<class RETURNTYPE> RETURNTYPE KeysAs() const;

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	template<class RETURNTYPE> RETURNTYPE ValuesAs() const
		///
		/// \brief	Returns the values packed into the specified data type if this is possible.
		///
		/// \author	Markus
		/// \date	21.02.2010
		///
		/// \return	The values of the dictionary as the specified data type.
		////////////////////////////////////////////////////////////////////////////////////////////////////
		template<class RETURNTYPE> RETURNTYPE ValuesAs() const;

	protected:

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	void SortIfDirty() const
		///
		/// \brief	Sorts if the dictionary if it is 'dirty'.
		///
		/// \author	Markus
		/// \date	21.02.2010
		////////////////////////////////////////////////////////////////////////////////////////////////////
		void SortIfDirty() const;

		Array<KeyValuePair<KEYTYPE, VALUETYPE> > keyValuePairs;
		bool inBulkInsert;
	};

	//------------------------------------------------------------------------------
	/**
	*/
	template<class KEYTYPE, class VALUETYPE>
	Dictionary<KEYTYPE, VALUETYPE>::Dictionary() :
		inBulkInsert(false)
	{
		// empty
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class KEYTYPE, class VALUETYPE>
	Dictionary<KEYTYPE, VALUETYPE>::Dictionary(const Dictionary<KEYTYPE, VALUETYPE>& rhs) :
		keyValuePairs(rhs.keyValuePairs),
		inBulkInsert(false)
	{
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class KEYTYPE, class VALUETYPE> void
	Dictionary<KEYTYPE, VALUETYPE>::operator=(const Dictionary<KEYTYPE, VALUETYPE>& rhs)
	{
		this->keyValuePairs = rhs.keyValuePairs;
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class KEYTYPE, class VALUETYPE> void
	Dictionary<KEYTYPE, VALUETYPE>::Clear()
	{
		this->keyValuePairs.Clear();
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class KEYTYPE, class VALUETYPE> tSize
	Dictionary<KEYTYPE, VALUETYPE>::Size() const
	{
		return this->keyValuePairs.Size();
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class KEYTYPE, class VALUETYPE> bool
	Dictionary<KEYTYPE, VALUETYPE>::IsEmpty() const
	{
		return (0 == this->keyValuePairs.Size());
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class KEYTYPE, class VALUETYPE> void
	Dictionary<KEYTYPE, VALUETYPE>::Add(const KeyValuePair<KEYTYPE, VALUETYPE>& kvp)
	{
		if (this->inBulkInsert)
		{
			this->keyValuePairs.Add(kvp);
		}
		else
		{
			this->keyValuePairs.InsertSorted(kvp);
		}
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class KEYTYPE, class VALUETYPE> void
	Dictionary<KEYTYPE, VALUETYPE>::Reserve(tSize numElements)
	{
		this->keyValuePairs.Reserve(numElements);
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class KEYTYPE, class VALUETYPE> void
	Dictionary<KEYTYPE, VALUETYPE>::BeginBulkAdd()
	{ 
		this->inBulkInsert = true;
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class KEYTYPE, class VALUETYPE> void
	Dictionary<KEYTYPE, VALUETYPE>::EndBulkAdd()
	{ 
		this->keyValuePairs.Sort();
		this->inBulkInsert = false;
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class KEYTYPE, class VALUETYPE> void
	Dictionary<KEYTYPE, VALUETYPE>::Add(const KEYTYPE& key, const VALUETYPE& value)
	{ 
		KeyValuePair<KEYTYPE, VALUETYPE> kvp(key, value);
		if (this->inBulkInsert)
		{
			this->keyValuePairs.Add(kvp);
		}
		else
		{
			this->keyValuePairs.InsertSorted(kvp);
		}
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class KEYTYPE, class VALUETYPE> void
	Dictionary<KEYTYPE, VALUETYPE>::Erase(const KEYTYPE& key)
	{ 
		tIndex eraseIndex = this->keyValuePairs.BinarySearchIndex(key);
	 
		this->keyValuePairs.EraseIndex(eraseIndex);
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class KEYTYPE, class VALUETYPE> void
	Dictionary<KEYTYPE, VALUETYPE>::EraseAtIndex(tIndex index)
	{ 
		this->keyValuePairs.EraseIndex(index);
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class KEYTYPE, class VALUETYPE> tIndex
	Dictionary<KEYTYPE, VALUETYPE>::FindIndex(const KEYTYPE& key) const
	{ 
		return this->keyValuePairs.BinarySearchIndex(key);
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class KEYTYPE, class VALUETYPE> bool
	Dictionary<KEYTYPE, VALUETYPE>::Contains(const KEYTYPE& key) const
	{ 
		return (InvalidIndex != this->keyValuePairs.BinarySearchIndex(key));
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class KEYTYPE, class VALUETYPE> const KEYTYPE&
	Dictionary<KEYTYPE, VALUETYPE>::KeyAtIndex(tIndex index) const
	{ 
		return this->keyValuePairs[index].Key();
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class KEYTYPE, class VALUETYPE> VALUETYPE&
	Dictionary<KEYTYPE, VALUETYPE>::ValueAtIndex(tIndex index)
	{ 
		return this->keyValuePairs[index].Value();
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class KEYTYPE, class VALUETYPE> const VALUETYPE&
	Dictionary<KEYTYPE, VALUETYPE>::ValueAtIndex(tIndex index) const
	{ 
		return this->keyValuePairs[index].Value();
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class KEYTYPE, class VALUETYPE> KeyValuePair<KEYTYPE, VALUETYPE>&
	Dictionary<KEYTYPE, VALUETYPE>::KeyValuePairAtIndex(tIndex index) const
	{ 
		return this->keyValuePairs[index];
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class KEYTYPE, class VALUETYPE> VALUETYPE&
	Dictionary<KEYTYPE, VALUETYPE>::operator[](const KEYTYPE& key)
	{
		int keyValuePairIndex = this->FindIndex(key);
	  
		return this->keyValuePairs[keyValuePairIndex].Value();
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class KEYTYPE, class VALUETYPE> const VALUETYPE&
	Dictionary<KEYTYPE, VALUETYPE>::operator[](const KEYTYPE& key) const
	{
		int keyValuePairIndex = this->FindIndex(key);
	 
		return this->keyValuePairs[keyValuePairIndex].Value();
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class KEYTYPE, class VALUETYPE>
	template<class RETURNTYPE>
	RETURNTYPE
	Dictionary<KEYTYPE, VALUETYPE>::ValuesAs() const
	{ 
		RETURNTYPE result(this->Size(),this->Size());
		tIndex i;
		for (i = 0; i < this->keyValuePairs.Size(); i++)
		{
			result.Append(this->keyValuePairs[i].Value());
		}
		return result;
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class KEYTYPE, class VALUETYPE>
	Array<VALUETYPE>
	Dictionary<KEYTYPE, VALUETYPE>::ValuesAsArray() const
	{
		return this->ValuesAs<Array<VALUETYPE> >();
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class KEYTYPE, class VALUETYPE> 
	template<class RETURNTYPE>
	RETURNTYPE
	Dictionary<KEYTYPE, VALUETYPE>::KeysAs() const
	{ 
		RETURNTYPE result(this->Size(),this->Size());
		tIndex i;
		for (i = 0; i < this->keyValuePairs.Size(); i++)
		{
			result.Append(this->keyValuePairs[i].Key());
		}
		return result;
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class KEYTYPE, class VALUETYPE>
	Array<KEYTYPE>
	Dictionary<KEYTYPE, VALUETYPE>::KeysAsArray() const
	{
		return this->KeysAs<Array<KEYTYPE> >();
	}

}

#endif // dictionary_h__